<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
  function BinarySerachTree(){
      function node(key){
        // 给定的二叉树的值为key
        this.key = key 
        // 并且有左右节点！
        this.left = null
        this.right = null
      }

    BinarySerachTree.prototype.insert = function(key){
        // 创建一个新的节点
        let newNode = new node(key)
        // 判断这个有没有这个头节点是否为null
        if(this.root ===null ){
          this.root = newNode
        }else{  //否则比较值，比较左右节点的大小而后进行插入
         this.insertNode(this.root,newNode)   //从头节点开始比较
        }
  }
  // 特别提醒：如果是递归给定退出条件，就可以递归下去了！ 
    BinarySerachTree.prototype.insertNode = function(node,newNode){
    // 如果说node比新插入节点小，看其是否为null
    if(newNode.key < node.key){
        if(node.left ===null ){
          // 让左节点直接指向新的节点
          node.left = newNode
        }else{
          // 无限比较左节点的值，是否符合退出条件,相当于一直用node.left.left.left.....和newNode进行比较直到找到位置
          this.insertNode(node.left,newNode)
        }
    }else{  //直接比较右节点的值，和上面的操作步骤类似
       if(node.right === null ){
         node.right = newNode
       }else{
         this.insertNode(node.right,newNode)
       }
    }
  }
  // 二叉树有一个特点就是，最左边的就是最小的值，最右边的值就是最大的
    BinarySerachTree.prototype.min = function(){
       let current = this.root
       while(current != null ){
         current = current.left
       }
       return current.key
   }

    BinarySerachTree.prototype.max = function(){
       let current = this.root
       while(current != null){
         current = current.right
       }
       return current.key
   }
    BinarySerachTree.prototype.search = function(key){
     let current = this.root
    if(current != null){
      if(current.key > key){
        current = current.left
      }
      else if(current.key < key ){
        current = current.right
      }else{
        return true
      }
    }
    return  false
   } 
    //方法1迭代！
    BinarySerachTree.prototype.remove = function(key){
      let current = this.root
      while(current){
        if(current.key > key){
          if(current.key = key){
              delete current.left
          }
          current = current.left
        }else{
          if(current.key = key){
             delete current.right
          }
          current = current.right
        }
      }
  
    }
  }
   //方法二递归





  </script>
</body>
</html>